#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int GetMidi(int* a,int begin,int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
		{
			return midi;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else
	{
		if (a[midi] > a[end])
		{
			return midi;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}
void swap(int* a, int* b)
{
	int tmp = 0;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
void QuickSort(int* a,int begin,int end)
{
	int left = begin;
	int right = end;
	if (left >= right)
	{
		return;
	}
	int midi = GetMidi(a, begin, end);
	swap(&a[midi], &a[begin]);
	int keyi = begin;
	while (right > left)
	{
		while (right > left && a[right] >= a[keyi])
		{
			right--;
		}
		while (right > left && a[left] <= a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[left]);
	keyi = left;
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
int main()
{
	int a[] = { 43,66,23,64,88,11,43,56,66,2,1 };
	int size = sizeof(a) / sizeof(a[0]);
	int i = 0;
	for (i = 0;i < size;i++)
	{
		printf("%5d", a[i]);
	}
	printf("\n");
	QuickSort(a,0,size-1);
	for (i = 0;i < size;i++)
	{
		printf("%5d",a[i]);
	}
	return 0;
}